package 搜索算法.广度优先搜索;


/**
 * 1. 问题描述
 *      求出一颗二叉树的最小深度
 *
 * 2. 算法分析
 *      1. 递归法，比较容易实现的一种算法
 *          因为一个二叉树的最小深度取决于左右子树的最小高度，所以采用递归实现，但是效率比较低
 *
 *      2. 采用非递归方式  栈或队列的方式实现
 *
 * 3. 代码实现
 */


class TreeNode1 {
    int val;
    TreeNode1 left;
    TreeNode1 right;
    TreeNode1() {}
    TreeNode1(int val) { this.val = val; }
    TreeNode1(int val, TreeNode1 left, TreeNode1 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

@SuppressWarnings("all")
public class 二叉树的最小深度 {
    public static void main(String[] args) {
        int[] nums = new int[10];
    }

    // 递归算法实现
    public int minDepth(TreeNode1 root) {

        if(root == null) {
            return 0; // 如果root为空
        }
        else if(root.left == null && root.right == null) {
            return 1;
        }
        int ans = Integer.MAX_VALUE;
        if(root.left != null) {
            ans = Math.min(ans,minDepth(root.left));
        }
        if(root.right != null) {
            ans = Math.min(ans,minDepth(root.right));
        }
        return ans+1;
    }

    // 使用栈

}
